/**
 * @Author Fizz Pu
 * @Date 2020/11/14 下午10:15
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，
 * 请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *  
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9, 3, 15 ,20, 7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


public class Leeoffer07 {

    static Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null  ||  preorder.length == 0)return null;
        for(int i = 0; i < inorder.length; ++i){
            map.put(inorder[i], i);
        }
        return helper(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }


    TreeNode helper(int[] preorder, int s, int e, int[] inorder, int start, int end){
        TreeNode root = null;
        if(s > e) return  root; // s,e表示前序数组中子树的下标范围
        int rootVal = preorder[s];// 取得根节点
        root = new TreeNode(rootVal);
        // int rootIndex = findIndex(rootVal, inorder, 0, inorder.length); //根节点在中序中的位置
        int rootIndex = map.get(rootVal);
        int leftCount = rootIndex - 1 - start + 1; // 左子树数量
        root.left = helper(preorder, s+1, s+1+leftCount - 1, inorder, start, rootIndex-1);
        root.right = helper(preorder,s + 1 + leftCount  ,e, inorder, rootIndex+1, end);
        return root;
    }

    private int findIndex(int val, int[] arr, int start, int end){
        for(int i = start; i < end; ++i){
            if(arr[i] == val)return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Leeoffer07 leeoffer07 = new Leeoffer07();
        TreeNode treeNode = leeoffer07.buildTree(new int[]{3,9,20,15,7}, new int[] {9,3,15,20,7});
        // TreeNode treeNode = leeoffer07.buildTree(new int[]{3}, new int[] {3});
        dfs(treeNode);
    }

    public static void dfs(TreeNode root){
        if(root == null) return;
        System.out.println(root.val);
        dfs(root.left);
        dfs(root.right);
    }
}

